/*
 *   AS IS License
 * ==Naive Coders==
 */
package org.naive.crunch;

import java.math.BigInteger;
import org.naive.data.Tree;
import org.naive.data.TreeAnnotation;

/**
 *
 * @author gbu.000
 */
public class Fragmenter {

    /**
     * How do we slice a tree? there are many ways to do this. are there?
     * curious curious.... why don't we just generate a binary number and spread
     * each bit over a node in the tree. nodes that have 1s assigned would
     * designate cut locations. mm how do you spread a binary number over a
     * tree? recursively? why not ? i mean sequence doesn't matter as long as we
     * guarantee that all possible ways of splitting a tree will be tried. mmm
     * this doesn't look good for big trees. each node doubles number of
     * possible divisions so for a tree that has 10 nodes we might end up with
     * 1024 ways of splitting. sure many divisions will contain single node
     * trees- we don't want that.
     */
    private final Tree mold;
    private final BigInteger mapEnd;
    private BigInteger fractureMap;

    public Fragmenter(Tree mold) {
        this.mold = mold;
        final int moldSize = mold.calcSize();
        mapEnd = new BigInteger(binString('1', moldSize));
        fractureMap = new BigInteger(binString('0', moldSize));
    }

    private String binString(char ch, int len) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            sb.append(ch);
        }
        return sb.toString();
    }

    public Tree next() {
        Tree n = mold.copy();
        fracture(n, 0);
        // TODO: horribly inefficient
        // replace big int with custom implementation of long binary
        // ---trivial
        fractureMap = fractureMap.add(new BigInteger("1"));

        if (mapEnd.compareTo(fractureMap) >= 0) {
            return n;
        }
        return null;
    }

    private int fracture(Tree t, int mapBitOffset) {
        int off = mapBitOffset + 1;
        if (fractureMap.testBit(mapBitOffset)) {
            t.putAnnotation(TreeAnnotation.FRAGMENT, mapBitOffset);
            for (Tree ct : t) {
                off = fracture(ct, off);
            }
        }
        return off;
    }
}
